/*CSC 362 Project 6: Sean Waitkus: This program creates an array of linked list structs
It generates a random number between 0 and 1,000,000 and places them in the appropriate 
list 0-10. It generates the size of each list and prints it out the list contents, 
the largest list size and the smallest list size. Finally it erases the lists
I want to note that I chose to allow the largest and smallest functions to return the 
largest and smallest values, while not completely neccesary it was simpler. I could have
manipulated the datum as pointers or not returned the values at all
The largest sized list I saw was a 20 and smallest was a 2. Without averaging them I would
say that I had an average largest of 12 and average smallest of 6*/

#include "stdafx.h"

void main(){

	//iteration variable
	int i = 0;
	//int to store the largest list created
	int Largest = 0;
	//int to store the smalles list created
	int Smallest = 0;
		//initializes the array of list structs based on tableLength #defined in the header
	struct list HashTable[tableLength];
	//seed the random number generator
	srand(time(NULL));
	//iterates through the array initializing its values
	while(i  < tableLength){
		//sets the size of the list to 0
		HashTable[i].size = 0;
		//initializes the first node to NULL
		HashTable[i].listNode = NULL;
		//increments the iteration variable
		i++;
	}
	//resets the iteration variable for the next loop
	i = 0;
	//iterates n times based on iterate #defined in the header
	while(i < iterate){
		//inserts the randomly generated value into the list array
		int r, bucket;
		r = rand() % maxNum;
		bucket = r % tableLength;
		HashTable[bucket].listNode = orderedInsert(HashTable[bucket].listNode, r);
		HashTable[bucket].size++;
		//increments the iteration variable
		i++;
	}
	i = 0;
	//loop for printing
	while(i < tableLength){
		//prints the lists and its size
		printf("%s %d\n", "List Index", i);
		printLists(HashTable[i].listNode);
		i++;	
	}
	i = 0;
	//gets and stores the largest list 
	Largest = findLargest(HashTable);
	//gets and stores the smallest list
	Smallest = findSmallest(HashTable);
	
	while(i < tableLength){
	
		//erases the lists
		destroyList(HashTable[i].listNode);
		HashTable[i].size = 0;
		i++;
	}


	scanf("%d", &i);

}

struct node * orderedInsert(struct node *listNode, int n){
	//determines the list to put the number in by modding the number by the table size
	//int bucket = n % tableLength;
	//creates a new node to be inserted into the list
	struct node *newNode = (struct node *)malloc(sizeof(struct node));
	//sets the element field of the node struct to the integer generated and its next pointer to null
	newNode->element = n;
	newNode->next = NULL;
	//checks if the current index node is null if true sets that to the newNode
	if(listNode == NULL){
		listNode = newNode;
		return listNode;
	
	
	}
	//if the new node is less than the first node
	else if (n < listNode->element){
		//creates a new temp node
		struct node *tempNode = (struct node *)malloc(sizeof(struct node));
		//sets the temp node to the first node value
		tempNode = listNode;
		//sets the first node to the new node
		listNode = newNode;
		//sets the first node before the newNode
		listNode->next = tempNode;
		return newNode;

	}

	else{
		//creates two temp nodes for swapping
		struct node *tempNode = (struct node *)malloc(sizeof(struct node));
		struct node *prevNode = (struct node *)malloc(sizeof(struct node));
		//temp node is now the first node
		tempNode = listNode;

		//traverse the list while temp is not null and its element is smaller than the new node's element
		while(tempNode != NULL && tempNode->element < n){
			//swap the tempNode(original first) node into prevNode
			prevNode = tempNode;
			//set tempNode(originally the first node) to its next node
			tempNode = tempNode->next;
		}
		//sets the new node before tempNode(originally the first node)
		newNode->next = tempNode;
		//sets the prevNode(now the first node) before the new node
		prevNode->next = newNode;
		
		
	}
	return listNode;
	//increments the list size
	//HashTable[bucket].size++;
}
//iterate through array and compare size values to find largest
int findLargest(struct list HashTable[]){
	//iteration variable
	int i = 0;
	//variable to store the size value
	int largest = 0;
	//iterates while less than the table length
	while(i < tableLength){
		//if the size of the list is greater than the largest found so far
		//sets largest to the size of the list
		if(HashTable[i].size > largest){
		largest = HashTable[i].size;
		}
		//increments the iteration variable
		i++;
	}
	//prints the largest list index found along with its size
	printf("%s %d\n", "The Largest List is index", largest);
	//returns the largest list found
	//LargestAverage = LargestAverage + largest;
	return largest;

}
//iterate through list and compare size values to find smallest
int findSmallest(struct list HashTable[]){
	//iteration variable
	int i = 0;
	//variable to store the smallest size found
	int smallest = 0;
	//iterates while less than the table length
	while(i < tableLength){
		//sets the first index's size to smallest IF i is 0, meaning first run.
		if(i == 0){
		smallest = HashTable[i].size;
		}
		//otherwise compare a given index's size to smallest and if smaller
		//sets smallest to equal that index's size
		else if(HashTable[i].size < smallest){
			smallest = HashTable[i].size;
		}
		//increments the iteration variable
		i++;
	}
	//prints out the smallest list index found along with its size
	printf("%s %d\n", "The Smallest List is index", smallest);
	//SmallestAverage = SmallestAverage + smallest;
	//returns the smallest list found
	return smallest;
}

//iterates through each list in the array and erases the nodes contained in each list
void destroyList(struct node *listNode){

		//creates a temporary node to set as the first node in the list
		struct node *tempNode = (struct node *)malloc(sizeof(struct node));
		//iterates until the first node in the list is null
		while( listNode != NULL){
			//sets the temp node to the first node in the list
			tempNode = listNode;
			//sets the first node in the list to the next node
			listNode = listNode->next;
			//erases the temp node from memory
			free(tempNode);
	
		}
	
}
//prints the array
void printLists(struct node *listNode){
	
		//creats a temporary node for printing
		struct node *tempNode = (struct node *)malloc(sizeof(struct node));
		//sets the temp node equal to the first node
		tempNode = listNode;
		while(tempNode != NULL){
			//prints the temp node
			printf("%s %s %d\n","List", "Contains",  tempNode->element);
			//sets the temp node to the next node in the list
			tempNode = tempNode->next;
	
		}
		

}